package com.wp;


class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

public class Solution {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(1);
        node1.next = node2;
        ListNode result = partition(node1, 2);
        while (result != null){
            System.out.println(result.val);
            result = result.next;
        }
    }
    public static ListNode partition(ListNode head, int x) {
        ListNode less = null, more = null, left = null, right = null;
        while (head != null) {
            if (head.val < x) {
                if (less == null) {
                    less = head;
                    left = less;
                } else {
                    left.next = head;
                    left = left.next;
                }
            } else {
                if (more == null) {
                    more = head;
                    right = more;
                } else {
                    right.next = head;
                    right = right.next;
                }
            }
            head = head.next;
        }
        if (left != null) {
            left.next = more;
            return less;
        }
        return more;
    }
}